/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

import org.junit.Test;

/**
 * <p>
 * 删除重复只保留没有重复的值 
 * Given 1->2->3->3->4->4->5, return 1->2->5. 
 * Given 1->1->1->2->3, return 2->3
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月20日
 */
public class RemoveDuplicatesFromSortedListII {

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode pre = head;
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            // 移动当前指针到重复元素的最后一个
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
            }
            if (pre == curr) {
                // 如果当前元素没有重复的，那么加入当前元素
                tail.next = pre;
                tail = tail.next;
            }
            pre = curr.next;
            curr = curr.next;
        }
        // 加入最后一个元素
        tail.next = curr;
        return dummy.next;
    }
    
    
    @Test
    public void testCase1(){
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next = new ListNode(3);
        
        ListNode node = deleteDuplicates(head);
        while(node!=null){
            System.out.print(" "+node.val+"\t");
            node = node.next;
        }
    }
}
